/* Author: DO HOAANG HAI
 * Main.java
 *
 * Created on June 4, 2006, 8:59 PM
 *
 * Description: This project demonstrates  how to use radix sort algorithm to sort an one-dimension array
 */

package radix;

/**
 *
 * @author hai
 */
public class Main {
    
    private static int[] array={123,432,832,827,910,201,482,852,273,273};
    /** Creates a new instance of Main */
    public Main() {
    }
    
    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        System.out.println("array to be sorted: ");
        displayResult();
        radixSort();
        System.out.println(" sorted array: ");
        displayResult();
    }
    public static void displayResult(){
        
        for (int i=0; i<array.length; i++)
            System.out.println("  "+ array[i]);
    }
    public static void radixSort(){
        int numOfDigits=3;
        List L=new List(array);
        List buck[]=new List[10];
        for (int i=0; i<10; i++){
            buck[i]=new List();
        }
        for (int digit=0; digit<numOfDigits; digit++){
            for (int i=0; i<10; i++){
                buck[i].clearList();
            }
           
            distribute(L,buck, digit);
            combine(L,buck);
        }
       
       Node cur=L.head;
       int i=0;
       while(cur!=null){
           array[i]=cur.value;
           cur=cur.next;
           i++;
       }
        
    }
    public static void distribute(List L, List[] buck, int digit){
        Node cur=L.head;
        while(cur!=null){
            int index=(cur.value%(int)(Math.pow(10,digit+1)))/((int)(Math.pow(10,digit)));
            
            buck[index].insert(new Node(cur.value));
            cur=cur.next;               
            }        
       
            
    }
    public static void combine(List L,List[] buck){
        L.clearList();
        for (int i=0; i<10; i++){
           
            Node cur=buck[i].head;
            while (cur!=null){
                L.insert(cur);
                cur=cur.next;
            }
        }
    }   
    public static void displayList(List l){
        Node cur=l.head;
        
        while(cur!=null){
            System.out.print("  "+cur.value);
        cur=cur.next;
        }
    }
       
    
}
class List{
    Node head;
    Node tail;
    
    public List(){
        head=tail=null;
    }
    public List(Node n){
        head=n;
        tail=n;
        while(n.next!=null)
            tail=n.next;
    }
    public List(int[] ar){
        head=new Node(ar[0]);
        Node current=head;
        for (int i=1; i<ar.length; i++){
            Node temp=new Node(ar[i]);
            current.setNext(temp);
            current=temp;            
        }
        tail=current;
            
    }
    public void insert(Node n){
        if (head==null){            
            head=n;
            tail=head;
        }
        else{
            tail.setNext(n);
            tail=tail.next;
        } 
        
    }
    public void clearList(){
        head=tail=null;
    }
}
class Node{
    int value;
    Node next;
    public Node(){
        value=0;
    }
    public Node(int value){
        this.value=value;
        
    }
    public void setNext(Node n){
        next=n;
    }

}
